package tree;


import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和
 * @author le
 */
public class RangeSumOfBinarySearchTree
{
    public static void main(String[] args)
    {

    }

    public int rangeSumBinarySearchTree(TreeNode root, int low, int high) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null){
            queue.offer(root);
        }
        int res = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                TreeNode tmp = queue.poll();
                if (tmp.val > low && tmp.val < high){
                    res += tmp.val;
                }
                if (tmp.left != null){
                    queue.offer(tmp.left);
                }
                if (tmp.right != null){
                    queue.offer(tmp.right);
                }
            }
        }
        return res;
    }
}
